package com.dubious.interview.graph;

import java.util.HashSet;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Queue;
import java.util.Set;

public final class Graphs {
    private Graphs() {
    }

    /**
     * transpose a graph backed by lists. O(V + E) runtime.
     */
    public static GraphByList<Integer, Integer> transpose(GraphByList<Integer, Integer> graph) {
        List<List<Edge<Integer>>> edges = graph.getEdges();

        GraphByList<Integer, Integer> transpose =
                new GraphByList<Integer, Integer>(edges.size());

        for (int i = 0; i < edges.size(); i++) {
            for (Edge<Integer> edge : edges.get(i)) {
                transpose.withEdge(edge.getVertexB(), edge.getVertexA(), edge.getWeight());
            }
        }

        return transpose;
    }

    /**
     * transpose a graph backed by matrices. O(V^2) runtime.
     */
    public static GraphByMatrix transpose(GraphByMatrix graph) {
        int[][] edges = graph.getEdges();

        GraphByMatrix transpose = new GraphByMatrix(edges.length);

        for (int i = 0; i < edges.length; i++) {
            for (int j = 0; j < edges.length; j++) {
                transpose.withEdge(j, i, edges[i][j]);
            }
        }

        return transpose;
    }

    /**
     * Undirect a multigraph - reduce multi edges into single undirected edges and eliminate
     * self-loops. O(V + E) runtime.
     */
    public static GraphByList<Integer, Integer> undirectGraph(GraphByList<Integer, Integer> graph) {
        List<List<Edge<Integer>>> edges = graph.getEdges();

        // iterate over the edges, generating equivalent undirected edges, using a Set to avoid
        // duplicates.
        Set<Edge<Integer>> newEdges = new HashSet<Edge<Integer>>();
        for (int i = 0; i < edges.size(); i++) {
            for (Edge<Integer> edge : edges.get(i)) {
                if (edge.getVertexA() != edge.getVertexB()) {
                    newEdges.add(new Edge<Integer>(edge.getVertexA(), edge.getVertexB(), 1));
                    newEdges.add(new Edge<Integer>(edge.getVertexB(), edge.getVertexA(), 1));
                }
            }
        }

        // put edges in the new graph
        GraphByList<Integer, Integer> undirected =
                new GraphByList<Integer, Integer>(edges.size());
        for (Edge<Integer> newEdge : newEdges) {
            undirected.withEdge(newEdge.getVertexA(), newEdge.getVertexB(), newEdge.getWeight());
        }

        return undirected;
    }

    /**
     * Find the square of a adjecenty-list-based graph. The square of a graph G=(V,E) is G^2=(V,E^2)
     * where E^2 = {(u,w) : there exists (u,v) in E and (v,w) in E}.
     * 
     * Runtime is O(E(V + E)) for multigraphs or O(V(V + E)) for simple directed graphs?
     */
    public static GraphByList<Integer, Integer> square(GraphByList<Integer, Integer> graph) {
        List<List<Edge<Integer>>> edges = graph.getEdges();

        Set<Edge<Integer>> newEdges = new HashSet<Edge<Integer>>();
        // iterate over the edges to construct squared edges, using a Set to avoid duplicates
        for (int i = 0; i < edges.size(); i++) {
            for (Edge<Integer> edge1 : edges.get(i)) {
                for (Edge<Integer> edge2 : edges.get(edge1.getVertexB())) {
                    newEdges.add(new Edge<Integer>(edge1.getVertexA(), edge2.getVertexB(), 1));
                }
            }
        }

        GraphByList<Integer, Integer> square = new GraphByList<Integer, Integer>(edges.size());
        for (Edge<Integer> newEdge : newEdges) {
            square.withEdge(newEdge.getVertexA(), newEdge.getVertexB(), newEdge.getWeight());
        }

        return square;
    }

    /**
     * Find the square of a adjecenty-matrix-based graph. The square of a graph G=(V,E) is
     * G^2=(V,E^2) where E^2 = {(u,w) : there exists (u,v) in E and (v,w) in E}.
     * 
     * Runtime is O(V^3).
     */
    public static GraphByMatrix square(GraphByMatrix graph) {
        int[][] edges = graph.getEdges();

        Set<Edge<Integer>> newEdges = new HashSet<Edge<Integer>>();
        // iterate over the edges to construct squared edges, using a Set to avoid duplicates
        for (int i = 0; i < edges.length; i++) {
            for (int j = 0; j < edges.length; j++) {
                if (edges[i][j] != 0) {
                    for (int k = 0; k < edges.length; k++) {
                        if (edges[j][k] != 0) {
                            newEdges.add(new Edge(i, k, 1));
                        }
                    }
                }
            }
        }

        GraphByMatrix square = new GraphByMatrix(edges.length);
        for (Edge<Integer> newEdge : newEdges) {
            square.withEdge(newEdge.getVertexA(), newEdge.getVertexB(), newEdge.getWeight());
        }

        return square;
    }

    /**
     * Find the tree that represents the result of a breadth-first search, where the weights of the
     * edges of the BFS tree are the distance from root to element in the original tree.
     * 
     * Runtime is O(V + E).
     */
    public static GraphByList<Integer, Integer> bfs(GraphByList<Integer, Integer> graph, int root) {
        List<List<Edge<Integer>>> edges = graph.getEdges();

        GraphByList<Integer, Integer> bfs = new GraphByList<Integer, Integer>(edges.size());
        boolean[] discovered = new boolean[edges.size()];
        int[] distance = new int[edges.size()];

        Queue<Integer> toProcess = new LinkedList<Integer>();
        discovered[root] = true;
        toProcess.offer(root);

        while (toProcess.size() > 0) {
            int vertex = toProcess.poll();
            for (Edge<Integer> edge : edges.get(vertex)) {
                int toVertex = edge.getVertexB();
                if (!discovered[toVertex]) {
                    // undiscovered vertex found
                    // put it in the queue to process
                    toProcess.offer(toVertex);
                    // mark as discovered and record the distance
                    discovered[toVertex] = true;
                    distance[toVertex] = distance[vertex] + 1;
                    // include this edge in the BFS
                    bfs.withEdge(vertex, toVertex, distance[toVertex]);
                }
            }
        }

        return bfs;
    }

    public static GraphByList<DFSVertexResult, Integer> dfs(
            GraphByList<Integer, Integer> graph,
            int startRoot) {
        List<List<Edge<Integer>>> edges = graph.getEdges();
        
        GraphByList<DFSVertexResult, Integer> dfs = new GraphByList<DFSVertexResult, Integer>(edges.size());
        // tracks "discovery" and "finish" of vertices
        int[] discovered = new int[edges.size()];
        int[] finished = new int[edges.size()];
        
        int currentRoot = startRoot;
        int traceCount = 1;
        while(traceCount < edges.size() * 2)
        {
            // loop to find the first undiscovered element after the currentRoot
            // when currentRoot is startRoot this will quickly give us startRoot
            for(int i = 0; i < edges.size(); i++)
            {
                int vertexToConsider = (currentRoot + i) % edges.size();
                if(discovered[vertexToConsider] == 0)
                {
                    currentRoot = vertexToConsider;
                    break;
                }
            }
            
            discovered[currentRoot] = traceCount++;
            traceCount = dfsRecurse(currentRoot, edges, dfs, discovered, finished, traceCount);
            finished[currentRoot] = traceCount++;
        }
        
        for(int i = 0; i < edges.size(); i++)
        {
            dfs.withVertexValue(i, new DFSVertexResult(discovered[i], finished[i]));
        }
        
        return dfs;
    }
    
    private static int dfsRecurse(int vertex, List<List<Edge<Integer>>> edges, GraphByList<DFSVertexResult, Integer> dfs, int[] discovered, int[] finished, int traceCounter)
    {
        // iterate over children in reverse order
        ListIterator iterator = edges.get(vertex).listIterator();
        
        while(iterator.hasNext())
        {
            int vertexB = ((Edge<Integer>)iterator.next()).getVertexB();
            if(discovered[vertexB] == 0)
            {
                // have found an undiscovered vertex
                // mark it as discovered
                discovered[vertexB] = traceCounter++;
                // add the edge
                dfs.withEdge(vertex, vertexB, 1);
                // recursively treat the child
                traceCounter = dfsRecurse(vertexB, edges, dfs, discovered, finished, traceCounter);
                finished[vertexB] =  traceCounter++;
            }
        }
        
        return traceCounter;
        
    }
}